/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 九转苍翎
 * Date: 2025/8/19
 * Time: 18:03
 */
public class Solution {
    public String minWindow(String s, String t) {
        int lenS = s.length(), lenT = t.length();
        int minLen = Integer.MAX_VALUE;
        int start = 0;
        int[] hash1 = new int[128];
        //将t放入容器
        for(int i = 0; i < t.length(); i++) {
            hash1[t.charAt(i)]++;
        }
        int[] hash2 = new int[128];
        for (int left = 0,right = 0,count = 0;right < lenS; right++) {
            char in = s.charAt(right);
            //进窗口
            hash2[in]++;
            //维护count
            if (hash1[in] >= hash2[in]) count++;
            if (count == lenT) {
                //更新最小子串,仅当前情况下更新start
                if(right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }
            }
            while(count == lenT){
                //出窗口
                char out = s.charAt(left);
                if (hash1[out] >= hash2[out]) count--;
                hash2[out]--;
                //更新最小子串,仅当前情况下更新start
                if (count + 1 == lenT) {
                    if(right - left + 1 < minLen) {
                        minLen = right - left + 1;
                        start = left;
                    }
                }
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        String ret = solution.minWindow("ADOBECODEBANC", "ABC");
        System.out.println(ret);
    }
}